#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

struct RouteEntry {
    string destination;
    int nextHop;
    int hops;
    int timestamp;
};

class Router {
private:
    int id;
    map<string, RouteEntry> routingTable;
    vector<int> neighbors;

public:
    Router(int routerId) : id(routerId) {}

    void addNeighbor(int neighborId) {
        neighbors.push_back(neighborId);
    }

    void addDirectRoute(const string& network, int hops) {
        RouteEntry entry = {network, id, hops, 0};
        routingTable[network] = entry;
    }

    void processUpdate(int fromNeighbor, const map<string, RouteEntry>& receivedTable) {
        for (const auto& [dest, entry] : receivedTable) {
            if (entry.nextHop == fromNeighbor) continue;

            int newHops = entry.hops + 1;
            if (routingTable.find(dest) == routingTable.end() || newHops < routingTable[dest].hops) {
                RouteEntry newEntry = {dest, fromNeighbor, newHops, 0};
                routingTable[dest] = newEntry;
                cout << "Router " << id << ": Updated route to " << dest 
                     << " via " << fromNeighbor << " (hops=" << newHops << ")" << endl;
            }
        }
    }

    map<string, RouteEntry> getRoutingTable() const {
        map<string, RouteEntry> filteredTable;
        for (const auto& [dest, entry] : routingTable) {
            if (entry.nextHop != id && entry.nextHop != 0) {
                filteredTable[dest] = entry;
            }
        }
        return filteredTable;
    }

    void printRoutingTable() const {
        cout << "\nRouter " << id << " Routing Table:" << endl;
        cout << "Destination\tNextHop\tHops" << endl;
        for (const auto& [dest, entry] : routingTable) {
            cout << dest << "\t\t" << entry.nextHop << "\t" << entry.hops << endl;
        }
    }
};

int main() {
    Router r1(1), r2(2), r3(3);

    r1.addDirectRoute("192.168.1.0/24", 0);
    r1.addDirectRoute("10.0.0.0/8", 0);
    r2.addDirectRoute("192.168.2.0/24", 0);
    r3.addDirectRoute("172.16.0.0/16", 0);

    r1.addNeighbor(2);
    r2.addNeighbor(1);
    r2.addNeighbor(3);
    r3.addNeighbor(2);

    cout << "Initial state:" << endl;
    r1.printRoutingTable();
    r2.printRoutingTable();
    r3.printRoutingTable();

    cout << "\n--- First Update Round ---" << endl;
    auto r2Table = r2.getRoutingTable();
    r1.processUpdate(2, r2Table);
    r3.processUpdate(2, r2Table);

    cout << "\n--- Second Update Round ---" << endl;
    auto r1Table = r1.getRoutingTable();
    auto r3Table = r3.getRoutingTable();
    r2.processUpdate(1, r1Table);
    r2.processUpdate(3, r3Table);

    cout << "\n--- Third Update Round ---" << endl;
    r2Table = r2.getRoutingTable();
    r1.processUpdate(2, r2Table);
    r3.processUpdate(2, r2Table);

    cout << "\nFinal state:" << endl;
    r1.printRoutingTable();
    r2.printRoutingTable();
    r3.printRoutingTable();

    return 0;
}